/*
 * @lc app=leetcode.cn id=738 lang=cpp
 *
 * [738] 单调递增的数字
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        std::stack<int> numStack;
        while (n > 0) {
            int mod = n % 10;
            numStack.push(mod);
            n /= 10;
        }
        
        while (!numStack.empty()) {
            inputNum.push_back(numStack.top());
            numStack.pop();
        }

        n_ = inputNum.size();
        // outputNum.resize(n_, 0);
        outputNum = inputNum;

        traceBack(0);

        // rebuild res here
        int result = 0;
        long int multi = 1;
        for (int i=outputNum.size()-1;i>=0;--i) {
            result += multi * outputNum[i];
            multi *= 10;
        }
        return result;
    }
private:
    bool traceBack(int index) {
        if (index == n_) {
            // finished
            return true;
        }

        // trying
        for (int i=outputNum[index];i>=currentMinNum;--i) {

// 借位了，后面就全从9开始
if (outputNum[index] != inputNum[index]) {
    for (int j=index+1;j<n_;++j) {
        outputNum[j] = 9;
    }
}
            outputNum[index] = i;
            // mark
            int previousMin = currentMinNum;
            currentMinNum = i > currentMinNum ? i : currentMinNum;
            if (traceBack(index+1)) {
                return true;
            }
            outputNum[index] = 0;
            currentMinNum = previousMin;
        }

        // can not find candidate num, failed
        return false;
    }
private:
    int currentMinNum = 0;
    int n_;
    std::vector<int> inputNum;
    std::vector<int> outputNum;
};
// @lc code=end

int main() {
    int n = 999998;
    Solution test;
    test.monotoneIncreasingDigits(n);
}